package br.univap.aed.cenario1.sort;

import java.util.ArrayList;


public class QuicksortInteiro {

	private int comparacoes = 0;
	private int copias = 0;

	public ArrayList<Integer> partition(ArrayList<Integer> vetor, int pivo) {

		if (vetor.size() == 0 || vetor.size() == 1) {
			return vetor;
		}

		ArrayList<Integer> L = new ArrayList<Integer>();
		ArrayList<Integer> E = new ArrayList<Integer>();
		ArrayList<Integer> G = new ArrayList<Integer>();
		
		Integer x, y;

		x = vetor.remove(pivo);
		E.add(x);

		while (!vetor.isEmpty()) {
			y = vetor.remove(0);

			if (y < x) {
				L.add(y);
				comparacoes++;
			} else if (y == x) {
				E.add(y);
				comparacoes++;
			} else if (y > x) {
				G.add(y);
				comparacoes++;
			}
		}

		vetor = merge(partition(L, sortear(L.size() - 1)), E,
				partition(G, sortear(G.size() - 1)));

		return vetor;
	}

	private ArrayList<Integer> merge(ArrayList<Integer> L, ArrayList<Integer> E, ArrayList<Integer> G) {
		ArrayList<Integer> v = new ArrayList<Integer>();

		while (!L.isEmpty()) {
			v.add(L.remove(0));
		}

		while (!E.isEmpty()) {
			v.add(E.remove(0));
		}

		while (!G.isEmpty()) {
			v.add(G.remove(0));
			
		}

		copias++;
		return v;
	}

	public static int sortear(int ate) {
		return (int) (Math.random() * ate);
	}

	public int getComparacoes() {
		return this.comparacoes;
	}

	public int getCopias() {
		return this.copias;
	}

}
